package com.leetcode.algorithm.y22.m08.w1;

import java.util.HashSet;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Set;

/**
 * 200. 岛屿数量
 * 
 * https://leetcode.cn/problems/number-of-islands/
 * 
 * @author jie.deng
 *
 */
class Question0200Solution02 {

	public int numIslands(char[][] grid) {
		// BFS
		int rows = grid.length;
		int cols = grid[0].length;
		int cnt = 0;
		int[][] directions = new int[][] { { 0, 1 }, { 0, -1 }, { 1, 0 }, { -1, 0 } };
		Set<Integer> visitedSet = new HashSet<>();
		Queue<int[]> queue = new LinkedList<>();
		for (int i = 0; i < rows; i++) {
			for (int j = 0; j < cols; j++) {
				int idx = getIdx(i, j, cols);
				if (grid[i][j] == '1' && visitedSet.add(idx)) {
					cnt++;
					queue.offer(new int[] { i, j });
					while (!queue.isEmpty()) {
						int[] arr = queue.poll();
						int row = arr[0];
						int col = arr[1];
						for (int[] dir : directions) {
							int r = row + dir[0];
							int c = col + dir[1];
							if (r >= 0 && r < rows && c >= 0 && c < cols) {
								idx = getIdx(r, c, cols);
								if (grid[r][c] == '1' && visitedSet.add(idx)) {
									queue.offer(new int[] { r, c });
								}
							}
						}
					}
				}
			}
		}
		return cnt;
	}

	private int getIdx(int row, int col, int cols) {
		return row * cols + col;
	}
}